package class1;

import common.ArrayUtils;

import java.util.Arrays;

public class TestDemo {
    static int[] model = {4,19,14,5,-3,1,8,5,11,15};
    static int[] arr = {4,19,14,5,-3,1,8,5,11,15};

    public static void main(String[] args) {
        Arrays.sort(model);
        ArrayUtils.printArr(model);

//        bubbleSort(arr);
//        selectSort(arr);
        heapSort(arr);
//        mergeSort(arr);
//        insertSort(arr);
        ArrayUtils.printArr(arr);
    }

    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int cur = arr[i];
            int j = i;
            while (j > 0 && arr[j - 1] > cur) {
                arr[j] = arr[j - 1];
                j--;
            }
            arr[j] = cur;
        }
    }

    // 选择排序
    public static void selectSort(int[] arr) {
        int min = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) { // 当 arr[j]的值比arr[min]还小，说明最小值是j
                    min = j;
                }
            }
            swap(arr, i, min);
        }
    }

    // 冒泡排序
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) { // 注意边界
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
            }
        }
    }

    // 堆排序
    public static void heapSort(int[] arr) {
        // 调整成大根堆
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
        int heapSize = arr.length - 1;
        heapify(arr, 0, heapSize);
        while (heapSize > 0) {
            swap(arr, 0, heapSize);
            heapify(arr, 0, heapSize--);
        }
    }

    // 上浮
    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    // 下沉
    public static void heapify(int[] arr, int index, int heapSize) {
        int left = (index << 1) | 1;
        while (left < heapSize) {
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left; // 取左右节点较大的
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, index, largest);
            index = largest;
            left = (index << 1) | 1;
        }
    }

    // 归并排序
    public static void mergeSort(int[] arr) {
        process(arr, 0, arr.length - 1);
    }

    public static void process(int[] arr, int l, int r) {
        if (l == r) {
            return;
        }
        int mid = l + ((r - l) >> 1);
        process(arr, l, mid);
        process(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }

    public static void merge(int[] arr, int l, int mid, int r) {
        int[] temp = new int[r - l + 1];
        int p1 = l, p2 = mid + 1;
        int index = 0;
        while (p1 <= mid && p2 <= r) {
            temp[index++] = arr[p1] >= arr[p2] ? arr[p2++] : arr[p1++];
        }
        while (p1 <= mid) {
            temp[index++] = arr[p1++];
        }
        while (p2 <= r) {
            temp[index++] = arr[p2++];
        }
        for (int i = 0; i < temp.length; i++) {
            arr[l + i] = temp[i];
        }
    }


    public static void swap(int[] arr, int x, int y) {
        int t = arr[x];
        arr[x] = arr[y];
        arr[y] = t;
    }
}
